package LeetCode;

import java.util.ArrayList;
import java.util.List;

public class LC_638_ShoppingOffers {

    public static void main(String[] args) {

    }

    public class Solution_1 {
        int ret = 0, base = 0;
        int[] buy;

        public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
            for (int i = 0; i < price.size(); i++) ret += price.get(i) * needs.get(i);
            base = ret;
            int[] most = new int[special.size()];
            for (int i = 0; i < most.length; i++) {
                List<Integer> t = special.get(i);
                int max = Integer.MAX_VALUE;
                for (int j = 0; j < t.size() - 1; j++) {
                    if (t.get(j) != 0)
                        max = Math.min(max, needs.get(j) / t.get(j));
                }
                most[i] = max;
            }

            buy = new int[most.length];
            dfs(price, special, needs, most, 0, new int[needs.size()]);
            return ret;
        }

        private void dfs(List<Integer> price, List<List<Integer>> special, List<Integer> needs, int[] most, int s, int[] have) {
            for (int i = 0; i < have.length; i++)
                if (have[i] > needs.get(i)) return;
            if (s == most.length) {
                int p = 0;
                for (int i = 0; i < buy.length; i++) {
                    List<Integer> tmp = special.get(i);
                    p += tmp.get(tmp.size() - 1) * buy[i];
                    for (int j = 0; j < tmp.size() - 1; j++) {
                        p -= buy[i] * tmp.get(j) * price.get(j);
                    }
                }
                ret = Math.min(ret, base + p);
                return;
            }

            for (int i = 0; i <= most[s]; i++) {
                int before = buy[s];
                buy[s] = i;
                int diff = i - before;
                for (int j = 0; j < special.get(s).size() - 1; j++)
                    have[j] += diff * special.get(s).get(j);
                dfs(price, special, needs, most, s + 1, have);
                for (int j = 0; j < special.get(s).size() - 1; j++)
                    have[j] -= buy[s] * special.get(s).get(j);
                buy[s] = 0;
            }
        }
    }

    public class Solution_2 {
        public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
            return shopping(price, special, needs, 0);
        }

        int shopping(List<Integer> price, List<List<Integer>> special, List<Integer> needs, int i) {
            if (i == special.size())
                return dot(needs, price);
            ArrayList<Integer> clone = new ArrayList<>(needs);
            int j = 0;
            for (j = 0; j < special.get(i).size() - 1; j++) {
                int diff = clone.get(j) - special.get(i).get(j);
                if (diff < 0)
                    break;
                clone.set(j, diff);
            }
            if (j == special.get(i).size() - 1)
                return Math.min(special.get(i).get(j) + shopping(price, special, clone, i), shopping(price, special, needs, i + 1));
            else
                return shopping(price, special, needs, i + 1);
        }

        int dot(List<Integer> a, List<Integer> b) {
            int sum = 0;
            for (int i = 0; i < a.size(); i++) {
                sum += a.get(i) * b.get(i);
            }
            return sum;
        }
    }
}